package letcode.oneQuestionPerDay._202004._20;

import java.util.*;

/**
 * @Description: 岛屿数量
 * @Date: 2020/4/20
 * @Author: 许群星
 */
public class IslandNumbers {
    public static void main(String[] args) {
        char[][] grid={{1,1,1,1,0},{1,1,0,1,0},{1,1,0,0,0},{0,0,0,0,0}};

        char[][] grid1={{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}};
        System.out.println(numIslands(grid));
    }
    //提供方法
    public static int numIslands(char[][] grid) {
        //定义set存放所有的1，queue遍历每一个岛屿
        Set<Integer> set=new HashSet<>();
        Queue<Integer> queue=new LinkedList<>();
        int n=grid.length;
        if (n==0)
            return 0;
        int m=grid[0].length;
        int[] dx={0,0,1,-1};//四个方向，不是八个方向
        int[] dy={1,-1,0,0};
        int ans=0;

        //找到所有的1，放入到队列中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]=='1'){
                    set.add(i*1000+j);
                }
            }
        }

        //为空返回0，不为空遍历
        if (set.isEmpty())
            return ans;

        while (!set.isEmpty()){
            Iterator<Integer> it=set.iterator();
            int temp=it.next();
            set.remove(temp);
            queue.offer(temp);
            while (!queue.isEmpty()){
                int haha=queue.poll();
                int x=haha/1000;
                int y=haha%1000;
                for (int i = 0; i < 4; i++) {
                    int tempx=x+dx[i];
                    int tempy=y+dy[i];
                    if (tempx<0||tempx>=n||tempy<0||tempy>=m)
                        continue;
                    int newTemp=tempx*1000+tempy;
                    if (set.contains(newTemp)){
                        queue.offer(newTemp);
                        set.remove(newTemp);
                    }
                }
            }
            ans++;
        }
        return ans;
    }
}
/*
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1
示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */